package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author haomin
 * @date 2023/03/22 21:15
 **/
public class Day3_22_Review {
    class CQueue1 {
        Deque<Integer> s1;
        Deque<Integer> s2;

        public void CQueue() {
            s1 = new LinkedList<>();
            s2 = new LinkedList<>();
        }

        public void appendTail(int value) {
            s1.push(value);
        }

        public int deleteHead() {
            if(s2.isEmpty()) {
                while(!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                if(s2.isEmpty()) return -1;
                else return s2.pop();
            }else return s2.pop();

        }
    }

    class Solution2 {
        public int fib(int n) {
            if(n <= 1) return n == 0 ? 0 : 1;
            int[] dp = new int[n+1];
            dp[0] = 0; dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
            }
            return dp[n];
        }
    }

    class Solution3 {
        int mod = (int)1e9 + 7;
        public int numWays(int n) {
            if(n <= 2) return n <= 1 ? 1 : 2;
            int[] dp = new int[n+1];
            dp[0] = 1; dp[1] = 1;
            for(int i = 2; i <= n; ++i) {
                dp[i] = (dp[i-1] + dp[i-2]) % mod;
            }
            return dp[n];
        }
    }

    class Solution4 {
        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode node1 = headA;
            ListNode node2 = headB;
            while(node1 != node2) {
                node1 = node1 == null ? headB : node1.next;
                node2 = node2 == null ? headA : node2.next;
            }
            return node1;
        }
    }

    public class Solution5 {
        public boolean hasCycle(ListNode head) {
            ListNode node1 = head;
            ListNode node2 = head;
            while(node2 != null && node2.next != null) {
                node1 = node1.next;
                node2 = node2.next.next;
                if(node1 == node2) return true;
            }
            return false;
        }
    }

    public class Solution6 {
        public ListNode detectCycle(ListNode head) {
            ListNode node1 = head;
            ListNode node2 = head;
            while(node2 != null && node2.next != null) {
                node1 = node1.next;
                node2 = node2.next.next;
                if(node1 == node2) {
                    ListNode node3 = head;
                    while(node1 != node3) {
                        node1 = node1.next;
                        node3 = node3.next;
                    }
                    return node1;
                }
            }
            return null;
        }
    }

}